Integer Programming Overview

Principles

Definition

Integer programming is a subfield of mathematical optimization focused on problems where some or all decision variables are restricted to be integers. This research area investigates theoretical properties and develops algorithms for finding optimal solutions to discrete optimization problems, which are essential for modeling scenarios involving indivisible entities, counts, or binary choices across numerous scientific and engineering disciplines.

Ontological type

Core Methods

Theoretical Foundations

Applications

Key developments

Key Figures

Enumeration and Dual Guidance era

Sartaj Sahni [1] was a key figure in the Enumeration and Dual Guidance era, with affiliations to Cornell University [3] and University of Minnesota [4] during this period. His contributions include P-Complete Approximation Problems [7] and Computing Partitions with Applications to the Knapsack Problem [8], which established early frameworks for bounding, partitioning, and problem decomposition that underpined later exact-solver advances. Egon Balas [2] emerged as a central figure with ties to Stanford University [5] and Carnegie Mellon University [6] in this era. His seminal works—An Additive Algorithm for Solving Linear Programs with Zero-One Variables [9], Intersection Cuts—A New Type of Cutting Planes for Integer Programming [10], and Discrete Programming by the Filter Method [11]—introduced additive solution methods, cutting planes, and filter approaches that shaped practical dual-guided bounding and pruning in subsequent solvers.

Structure-Exploiting Decomposition era

Fred Glover [1] was a leading figure in the Structure-Exploiting Decomposition era, with affiliations spanning the University of Colorado Boulder [3] and the University of Colorado Denver [4]. His key contribution this era is the development of Tabu Search—Part II [7], which extended metaheuristic search to structured combinatorial problems and inspired practical, structure-aware search strategies. Alexander Schrijver [2] was associated with Princeton University [5] and Yale University [6] during this period. Alexander Schrijver [2]'s Theory of Linear and Integer Programming [8] laid foundational theory for linear and integer programming and polyhedral approaches, enabling later reformulations and decomposition techniques central to this era.

Decomposition-Driven Hybrid Routing era

Michel Gendreau [1] has been a central figure in the Decomposition-Driven Hybrid Routing era, with affiliations at Université Laval [3] and Université de Montréal [4] during this period. His key contributions include the development of an exact algorithm for the elementary shortest path problem with resource constraints [9], together with the Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms [7] and Part II: Metaheuristics [8], which were instrumental in translating complex routing problems into decomposition-friendly formulations and guiding bounded, scalable solution approaches. Olli Bräysy [2] is likewise a leading contributor, with positions at Vrije Universiteit Amsterdam [5] and University of Jyväskylä [6] in this era. His work on the same VRP time-window problems through Part I [7] and Part II [8] helped couple local-search and metaheuristic strategies with decomposition-inspired structures, advancing practical scalability while preserving algorithmic bounds.